package com.jp.algorithm;

public class RegularExpression {


    public static boolean isMatch(char[] string, char[] pattern, int i, int j) {
        int m = string.length;
        int n = pattern.length;
        if (j == n) {
            return i == m;
        }

        //下一个字符不是'*'
        if (j == n - 1 || pattern[j + 1] != '*') {
            return i < m && string[i] == pattern[j] && isMatch(string, pattern, i + 1, j + 1);
        } else if (pattern[j + 1] == '*') { // 下一个字符是'*'
            while (i < m && (pattern[i] == '.' || string[i] == pattern[j])) {
                if (isMatch(string, pattern, i, j + 2)) {
                    return true;
                }
            }
        }
        //下一个字符是'*',但是当前不匹配
        return isMatch(string, pattern, i, j + 2);
    }
}
